package erfen;

/**
 * 我们希望始终保持：
 * nums[left .. right]  里一定包含最小值；
 * nums[right]  永远来自右半段（比最小值大）。
 * 只要这两点成立，循环结束时  left  必落在最小值位置。
 */
public class Solution_153 {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            // 提前终止条件：若区间已有序，直接返回左端点
            int mid = (left + right) >>> 1;
            if (nums[mid] > nums[right]) {
                left = mid + 1;  // 最小元素在右侧
            } else {
                right = mid;      // 最小元素在左侧或为mid
            }
        }
        return nums[left];  // 循环结束时left指向最小元素
    }
}
